package com.learn.algorithm.recursive;

import com.learn.algorithm.Sort;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LeetCode46 {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        f(nums, 0, result);
        return result;
    }

    public static void f(int[] nums, int i, List<List<Integer>> result) {
        if (i == nums.length) {
            List<Integer> one = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                one.add(nums[j]);
            }
            result.add(one);
        } else {
            Set<Integer> set = new HashSet<>();
            for (int j = i; j < nums.length; j++) {
                if (!set.contains(nums[j])) {
                    set.add(nums[j]);
                    swap(nums, i, j);
                    f(nums, i + 1, result);
                    swap(nums, i, j);
                }
            }
        }
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        List<List<Integer>> result = permute(new int[]{1, 2, 3});
        System.out.println(result);
    }
}
